package org.zhs.sort;


import java.util.Arrays;
import java.util.Random;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * 冒泡排序
 * 思想： 将相邻的两个元素比较，然后调换位置，直到数组有序。
 *
 * [5,2,8,9,1]
 * 第一趟遍历： [2,5,8,1,9]
 * 第二趟遍历： [2,5,1,8,9]
 * 第三趟遍历： [2,1,5,8,9]
 * 第四趟遍历: [1,2,5,8,9]
 *
 * 由上面变化可见，冒泡排序需要执行 n * (n - 1) / 2 次
 * 原因是： 冒泡排序实际上是 将数组中第 x 个元素，与数组中挨个对比，将对比的最小的值，放置到 x 位置上
 *         第二次遍历为第 x + 1 个元素，与数组中除去 x 之外的元素对比 ........
 *         .........................
 */
public class BubbleSort {

    public static void main(String[] args) {
        int[] array = IntStream.generate(() -> new Random().nextInt(100)).limit(20).toArray();
        System.out.println("before sorted :" + Arrays.stream(array).boxed().collect(Collectors.toList()));

        for (int outerIndex = 0; outerIndex < array.length; outerIndex++) {
            for (int innerIndex = outerIndex + 1; innerIndex < array.length; innerIndex++) {
                int temp = array[outerIndex];
                if (array[outerIndex] > array[innerIndex]) {
                    array[outerIndex] = array[innerIndex];
                    array[innerIndex] = temp;
                }
            }
        }

        System.out.println("after sorted :" + Arrays.stream(array).boxed().collect(Collectors.toList()));
    }

}
